/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package players;

import java.util.List;
import java.util.Iterator;
import java.util.Random;

import data.Line;
import interfaces.GameState;

/**
 *
 * @author Bruno
 */
public class MinimaxAlfaBeta extends AbstractPlayer {
    private int maxDepth, maxPoints, hfThreshold, rl,
                currentPlayer;
    
    private long GENERATED_STATES;
    
    @Override
    public Line makeMove(GameState gs) {
        maxDepth        = depthHeuristic(gs);
        hfThreshold     = hfThresholdHeuristic(gs);
        maxPoints       = gs.getSize().width * gs.getSize().height;
        rl              = gs.getRemainingLines().size();
        currentPlayer   = gs.getPlayer();
        
        return findBestMove(gs);
    }
    
    private Line findBestMove(GameState gs) {
        List<Line>  availableMoves  = gs.getRemainingLines();
        Line        bestMove        = null;
        int         bestScore       = Integer.MIN_VALUE,
                    counter         = 0;
        
        GENERATED_STATES = 0;
        
        System.out.print("THINKING...\n\nDepth: " + maxDepth + "\nHF Threshold: " + hfThreshold + "\n\n");
        
        Iterator<Line> it = availableMoves.iterator();
        while(it.hasNext()) {
            Line        line        = it.next();
            GameState   auxgs       = gs.clone(); ++GENERATED_STATES;
            int         tempscore   = 0;
            
            if(auxgs.addLine(line) > 0) // Se pontuou, max de novo
                tempscore = max(auxgs, 1, Integer.MAX_VALUE, bestScore);
            else // Caso contrário, vez do min
                tempscore = min(auxgs, 1, Integer.MAX_VALUE, bestScore);
            
            if(tempscore == Integer.MAX_VALUE) {
                // Caso tenha encontra um movimento que certamente conduzirá à vitória
                
                bestMove    = line;
                bestScore   = tempscore;
                
                break;
            } else if(tempscore > bestScore) {
                // Caso encontre um movimento melhor do que o movimento que já tem
                
                bestMove    = line;
                bestScore   = tempscore;
            } else if(tempscore == Integer.MIN_VALUE) {
                // Caso qualquer opção de movimento conduz certamente à derrota
                
                if(bestMove == null) {
                    Random random = new Random();
                    
                    if(availableMoves.size() > 1)
                        bestMove = availableMoves.get(random.nextInt(availableMoves.size() - 1));
                    else
                        bestMove = availableMoves.get(0);
                }
            }
            
            System.out.format("%6.2f %c (%,d) %d%n", (double)(++counter) * 100 / (double)(availableMoves.size()), '%', GENERATED_STATES, tempscore);
        }
        
        System.out.print("\nBest reachable pontuation AI can see: " + bestScore + "\n\n#=====#=====#=====#=====#=====#\n\n");
        
        return bestMove;
    }
    
    private int max(GameState gs, int depth, int minObtained, int maxObtained) {
        // Se ainda não atingiu a profundidade máxima
        if(depth <= maxDepth) {
            int remainingPoints = maxPoints - gs.player1Score() - gs.player2Score();
            
            // Verifica se o jogo está num estado irreversível
            if(gs.player1Score() - gs.player2Score() > remainingPoints ||
               gs.player2Score() - gs.player1Score() > remainingPoints) {
                return calcIrreversibleScore(gs);
            } else {
                // Jogo ainda não foi decidido
                
                List<Line> remainingMoves   = gs.getRemainingLines();
                int             bestScore   = Integer.MIN_VALUE;
                
                // Se não há movimentos possíveis, calcula a pontuação e retorna
                if(remainingMoves.size() <= 0)
                    return calcScore(gs);
                
                Iterator<Line> it = remainingMoves.iterator();
                while(it.hasNext()) {
                    Line        line        = it.next();
                    GameState   auxgs       = gs.clone(); ++GENERATED_STATES;
                    int         tempscore   = 0;
                    
                    if(auxgs.addLine(line) > 0) {
                        tempscore = max(auxgs, rl < hfThreshold ?
                                                (depth == maxDepth ? depth : depth + 1) :
                                                depth + 1,
                                                minObtained, maxObtained);
                    } else {
                        tempscore = min(auxgs, depth + 1, minObtained, maxObtained);
                    }
                    
                    // Poda alpha-beta
                    
                    // Caso tenha obtido uma pontuação melhor do que o mínimo
                    // Já encontrado por algum min antecessor
                    if(tempscore >= minObtained) {
                        return tempscore;
                    } else if(tempscore > bestScore) {
                        // Caso a pontuação não seja maior que um mínimo
                        // de algum min antecessor
                        // E seja melhor do que já foi encontrado para esse nível
                        
                        bestScore = tempscore; // Atualiza melhor pontuação
                        
                        // Atualiza localmente o máximo obtido
                        if(bestScore > maxObtained)
                            maxObtained = bestScore;
                    }
                }
                
                // Melhor pontuação detectada e retornando
                return bestScore;
            }
        } else {
            // Caso tenha ultrapassado a profundidade máxima
            // Avalia a pontuação do estado
            
            return calcScore(gs);
        }
    }
    
    private int min(GameState gs, int depth, int minObtained, int maxObtained) {
        // Se ainda não atingiu a profundidade máxima
        if(depth <= maxDepth) {
            int remainingPoints = maxPoints - gs.player1Score() - gs.player2Score();
            
            // Verifica se o jogo está num estado irreversível
            if(gs.player1Score() - gs.player2Score() > remainingPoints ||
               gs.player2Score() - gs.player1Score() > remainingPoints) {
                return calcIrreversibleScore(gs);
            } else {
                // Jogo ainda não foi decidido
                
                List<Line> remainingMoves   = gs.getRemainingLines();
                int             bestScore   = Integer.MAX_VALUE;
                
                // Se não há movimentos possíveis, calcula a pontuação e retorna
                if(remainingMoves.size() <= 0)
                    return calcScore(gs);
                
                Iterator<Line> it = remainingMoves.iterator();
                while(it.hasNext()) {
                    Line        line        = it.next();
                    GameState   auxgs       = gs.clone(); ++GENERATED_STATES;
                    int         tempscore   = 0;
                    
                    if(auxgs.addLine(line) > 0) {
                        tempscore = min(auxgs, rl < hfThreshold ?
                                                (depth == maxDepth ? depth : depth + 1) :
                                                depth + 1,
                                                minObtained, maxObtained);
                    } else {
                        tempscore = max(auxgs, depth + 1, minObtained, maxObtained);
                    }
                    
                    // Poda alpha-beta
                    
                    // Caso tenha obtido uma pontuação pior do que o máximo
                    // Já encontrado por algum max antecessor
                    if(tempscore <= maxObtained) {
                        return tempscore;
                    } else if(tempscore < bestScore) {
                        // Caso a pontuação não seja menor que um máximo
                        // de algum max antecessor
                        // E seja pior do que já foi encontrado para esse nível
                        
                        bestScore = tempscore; // Atualiza a pior pontuação (que seria bom para o min)
                        
                        // Atualiza localmente o mínimo obtido
                        if(bestScore < minObtained)
                            minObtained = bestScore;
                    }
                }
                
                // Retornando a melhor (pior no caso do min) pontuação detectada
                return bestScore;
            }
        } else {
            // Caso tenha ultrapassado a profundidade máxima
            // Avalia a pontuação do estado
            
            return calcScore(gs);
        }
    }
    
    private int calcScore(GameState gs) {
        if(currentPlayer == 1) {
            return gs.player1Score() - gs.player2Score();
        } else {
            return gs.player2Score() - gs.player1Score();
        }
    }
    
    private int calcIrreversibleScore(GameState gs) {
        if(calcScore(gs) > 0)
            return Integer.MAX_VALUE;
        else
            return Integer.MIN_VALUE;
    }
    
    private int depthHeuristic(GameState gs) {
        int depth, bonus, remainingMoves, boardSize, totalMoves;
        
        remainingMoves  = gs.getRemainingLines().size();
        boardSize       = gs.getSize().height * gs.getSize().width;
        totalMoves      = gs.getSize().width * (gs.getSize().height + 1) +
                          gs.getSize().height * (gs.getSize().width + 1);
        
        bonus = (int)java.lang.Math.floor(2.0 * (double)totalMoves / (double)remainingMoves);
        
        if(boardSize > 36) {
            depth = 1;
            bonus -= 1;
        } else if(boardSize > 25) {
            depth = 2;
            bonus -= 1;
        } else if(boardSize > 16) {
            depth = 2;
            bonus -= 1;
        } else if(boardSize > 9) {
            depth = 5;
            bonus -= 1;
        } else {
            depth = 6;
        }
        
        return depth + bonus;
    }
    
    private int hfThresholdHeuristic(GameState gs) {
        int hft =  (int) Math.ceil((double)(gs.getSize().width * (gs.getSize().height + 1) + gs.getSize().height * (gs.getSize().width + 1)) * 0.45);
        
        if(hft > 15)
            hft = 15;
        
        return hft;
    }

    @Override
    public String getName() {
        return "AlfaBeta";
    }
    
}